import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 剑指 Offer 60. n个骰子的点数
 * https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/
 */
public class Solutions_Offer_60 {
    public static void main(String[] args) {
        int n1 = 1;  // output: {0.16667, 0.16667, 0.16667, 0.16667, 0.16667, 0.16667}
        int n2 = 2;  // output: {0.02778, 0.05556, 0.08333, 0.11111, 0.13889, 0.16667, 0.13889, 0.11111, 0.08333, 0.05556, 0.02778}
        int n3 = 3;  // output: {0.02778, 0.05556, 0.08333, 0.11111, 0.13889, 0.16667, 0.13889, 0.11111, 0.08333, 0.05556, 0.02778}

        List<Integer> inputs = new ArrayList<>();
        inputs.add(n1);
        inputs.add(n2);
        inputs.add(n3);

        for (int input : inputs) {
            double[] result = dicesProbability(input);
            System.out.println(Arrays.toString(result));
        }
    }

    /**
     * 解题思路：动态规划（类似零钱兑换）
     * n 个骰子最多摇到 n * 5 + 1 种点数
     */
    public static double[] dicesProbability(int n) {
        double[] res = new double[6];
        Arrays.fill(res, 1.0 / 6.0);
        for (int i = 2; i <= n; i++) {
            double[] dp = new double[i * 5 + 1];
            for (int j = 0; j < res.length; j++) {
                for (int k = 0; k < 6; k++) {
                    // 正向推导
                    dp[j + k] += res[j] * (1.0 / 6.0);
                }
            }
            res = dp;
        }
        return res;
    }
}
